B+ Tree
B+Treeは常にすべての値をリーフブロックに持っている
pros 最悪のアクセス回数が小さい
cons どのようなデータでも必ずリーフまでアクセスする必要がある
多分木なので探索の計算量は$ O(\rm{log}_mN) B+Tree の実装については上記の講義動画に加え、Modern B-Tree Techniques という本が非常に参考になりました。
200ページに渡ってほぼ B-Tree についてのみ書かれているのですが、その分非常に丁寧でだいたい全部書いてあるのでおすすめです。